package leetCode.solution;

import java.util.HashMap;
import java.util.Map;

/**
你和你的朋友，两个人一起玩 Nim 游戏：

桌子上有一堆石头。
你们轮流进行自己的回合， 你作为先手 。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
 */
public class Solution292 {

	public boolean canWinNim(int n) {
		Map<String, Boolean> map = new HashMap<String, Boolean>();
		return process1(n, map);
    }
	
	// 先手函数 
	private boolean process1(int n, Map<String, Boolean> map) {
		if(n<=3) return true;
		if(map.containsKey(n+"-1")) return map.get(n+"-1");
		boolean falg = process2(n-1, map) || process2(n-2, map) || process2(n-3, map);
		map.put(n+"-1", falg);
		return falg;
	}
	
	// 后手函数
	private boolean process2(int n, Map<String, Boolean> map) {
		if(n<=3) return false;
		if(map.containsKey(n+"-2")) return map.get(n+"-2");
		boolean falg = process1(n-1, map) && process1(n-2, map) && process1(n-3, map);
		map.put(n+"-2", falg);
		return falg;
	}
	
	public static void main(String[] args) {
		int n = 0;
		System.out.println(new Solution292().isPowerOfTwo(n));
//		System.out.println(new Solution292().canWinNim(6));
//		System.out.println(new Solution292().process2(4,new HashMap<Integer, Boolean>()));
	}
	
	public boolean isPowerOfTwo(int n) {
        return (n&(~n+1))==n;
    }
}